1. Field of the Invention
This invention relates to electronic filters and particularly to an adaptive recursive filter which, by observing the input data to the recursive filter and using the least mean square error criterion, automatically updates weight vectors by using a simple iterative gradient search procedure in order to minimize the mean square error of the output data of the adaptive recursive filter.
2. Description of the Prior Art
Many types of prior art filters or filter systems have been proposed for filtering out or minimizing the errors caused by distortion or contamination of data introduced into that data when that data is transmitted through a transmission medium or channel, such as a radio propagation path, telephone lines, a cable television network, or a waterway. The contamination of the transmitted data can be caused by, for example, noise amplitude distortion, delay distortion, interference, data dispersion and redundant information. The data received from the transmission medium is rarely the same as the pre-transmitted data, due to the corruption of the data by the transmission medium. As a result, various devices and techniques have been utilized or proposed to minimize or compensate for the undesired effects of such data contamination or distortion.
In one type of system, if the characteristics of the transmission medium are known, the minimization of the distortion of the data by the transmission medium can be accomplished by predistorting the data to be transmitted in a way such that the additional distortion by the transmission medium alters the predistorted data signal to produce a received signal having the desired waveshape. However, use of this technique is limited to those situations where the characteristics of the transmission medium are constant and known in advance.
In another type of system, not only must the characteristics of the transmission medium be constant and known in advance, but much information must be known in advance about the data being transmitted and about the parameters that are to be extracted or estimated from the transmitted data. If these are known in advance, the entire filter system or filter device at the receiver end can be designed in advance with fixed, non-variable components to perform a desired function or operation. In such a case, a fixed parameter transversal filter or a fixed parameter recursive filter may be utilized to minimize the distortion and achieve the desired operation. Since a fixed parameter filter is designed for a particular situation or operation, any changes that may occur in the transmission medium or transmitted data will detrimentally affect the performance of the filter in the operation for which it was designed.
Such stability and pre-knowledge of the transmission medium characteristics, as well as pre-knowledge of the transmitted data and parameters to be extracted from such data, is often not found or known in advance. This is due to the fact that the transmission medium characteristics are either unknown or changing and/or advance information on the data being transmitted is unknown or in doubt. However, the received data may still have to be filtered to obtain certain properties of the received data that can still be utilized, even though, for example, particular values of the data are unknown.
As a result, for these applications, an adaptive filter may be needed to meet one or more operational requirements or functions. Generally an adaptive filter simultaneously estimates what is required to minimize the errors in the received data, based on observations of the data itself and some iterative procedure which converges to what the best filter would have been for a desired function. So basically, an adaptive filter selects its parameter values based on observations of the incoming or received data. Many types of adaptive filters have been proposed.
In U.S. Pat. No. 3,750,024 (Dunn et al) an adaptive filter is used in each of the transmitter and receiver portions of the overall system. A transmit filter in the transmitter monitors samples of the input signal to be transmitted in order to determine redundant information in the input signal and then removes the redundant information to produce a residual signal. At least one parameter of the redundant information is also determined. This parameter and the residual signal are multiplexed for transmission. The transmitted signal is demultiplexed in a receiver, with the resultant parameter and residual signal being used to control the operation of a receive filter and hence the subsequent reconstruction of the speech for utilization. In this system the transmit filter uses only input samples. No feedback path is provided between the output of the transmitter and the transmit filter to modify any filter parameters. As taught in Dunn et al, the digitally converted speech information is directly processed to develop the redundant information which is subtracted from the digitally converted speech. The filter coefficients in Dunn et al are developed by directly analyzing the speech information. More specifically, the filter coefficients are adjusted to the input signal by computing a short term correlation function from the input samples. The best fit of the filter's response to the input spectrum is obtained by minimizing the mean square value of the output signal of the transmit filter with respect to each of the weights to subsequently lead to the optimum weights. Inverse filters are used in both the transmitter and receiver of this system. No recursive filters are used in this system.
An article by Atal and Schroeder is referenced in Column 2, line 50 et seq. of Dunn et al. This article deals with a predictive quantizer system which, like that of Dunn et al, uses short term correlation in its system operation. The system in the cited article uses only output samples to drive the predictor, whereas the system of Dunn et al uses only input samples. Neither of these systems utilizes both input and output samples in its operation.
Another approach is briefly described in Column 5, line 8 et seq. of Dunn et al, wherein a prior art system is described as monitoring the level of the prediction and comparing it to the level of the input signal. In this approach, if the level of the prediction is not less than the level of the input signal with which it is being compared, the system assumes something is wrong, and forces the prediction to zero at that time. There appear to be two ways of forcing the prediction to zero. The system can either force all filter states to zero or force all filter coefficients to zero in order to zero the prediction. However, as indicated in Column 5, lines 14-17 of Dunn et al, this operation would diminish the advantage of having the prediction in the first place. It would further act to increase the error in the final output during the time that the system is forcing the prediction to zero, since nothing would be compared to the level of the input signal at that time.
Another system is described in U.S. Pat. No. 3,745,562 (Rosenbaum). Rosenbaum teaches an analog-to-digital encoder which uses an N dimensional quantizer to generate, from an input analog signal, N digits of an output code for transmission. An error signal, derived from past and future inputs, is applied to a tapped delay line, the outputs of which are multiplied by a coefficient for correcting errors in the input signal. However, the error signal is not utilized to adjust filter parameters.
Another technique to automatically correct for distortion introduced into a transmission medium involves the use of adaptive transversal filters or equalizers. An adaptive transversal filter comprises a tapped delay line and a plurality of multipliers, each associated with a single tap of the delay line. Each of the multipliers adjusts the amplitude and polarity of the signal obtained from the delay line at its associated tap. The outputs of these multipliers are then summed to provide the transversal filter output. By appropriate selection of the tap intervals and the multiplication factors, or tap gains, associated with each of the taps, the transversal filter may be used to accomplish intersymbol interference cancellation. That is, by selecting the amplitude characteristics of the multipliers to correspond to, for example, the impulse response characteristics of the transmission medium or line being used, the transversal filter effectively eliminates the ring-out associated with a digital pulse transmitted over the line. Many adaptive transversal filters or systems utilizing adaptive transversal filters have been devised to adjust automatically or adaptively the tap gains of the transversal filter such that some performance criterion is satisfied. Some examples of such transversal equalizer systems may be found in U.S. Pat. Nos. 3,368,168; 3,414,819; 3,414,845; 3,571,733; 3,651,316; 3,694,752; 3,708,766; 3,727,153; 3,736,414; 3,809,923; and 3,864,632. Most of these systems involve iterative methods, such as various gradient methods of equalization, which may be applied in the time domain or in the frequency domain. A non-iterative method may also be utilized. The difference between the iterative and non-iterative methods is that the iterative method uses signal samples both before and after the equalization, while the non-iterative method uses only the signal samples before the equalization.
A different type of adaptive transversal filter is described by B. Widrow in the article "Adaptive Filters", in Aspects of Networks and System Theory, ed. R.E. Kalman and N. De Claris, Holt, Reinhart and Winston, New York, 1970. In this article Widrow describes an adaptive transversal filter which, based upon observations of the input data, and a reference waveform correlated with some component of the input data, utilizes a least mean square error criterion to cause his adaptive transversal filter to converge. Thus, Widrow with his least mean square error criterion adjusts the weighted taps in his transversal filter to converge on the average to an estimate of the Wiener Filter which, in turn, is a relatively standard filter in the theory of filter design.
The problem with all of the previously discussed and identified transversal filters, including Widrow's adaptive transversal filter, is that such transversal filters are limited to have a finite impulse response. This finite impulse response is due to the fact that transversal filters can only produce zeros, and no poles, in the filter transfer function.
A transversal filter can only produce zeros, or zero gains at certain frequencies. It cannot have an essentially infinite gain at any frequency. In addition, the largest gain that a transversal filter can produce is a function of how many taps that the filter has. There are applications where it may be necessary to have points in the transfer function of a filter that have essentially infinite gains at one or more particular frequencies. In filter theory these high gain points are called "poles". The inability of a transversal filter to develop poles limits its usefulness in various applications. For example, the fact that a transversal filter can only produce zeros, and not poles, limits the capability of adaptive transversal filters when performing broadband noise cancellation, for which a channel transfer function which has zeros may have to be inverted.
Another prior art type of filter which could be used to correct for distortion is a non-adaptive, fixed parameter recursive filter. One type of non-adaptive, fixed parameter recursive filter is described in U.S. Pat. No. 3,703,632. The filter coefficients in this patent are stored in a memory from an unknown external source, while the input data is stored in another memory. A particular sequence of computation is disclosed wherein the stored filter coefficients and stored input data are selectively read out of the two memories to produce two separate signals in two separate channels, with the products of these two separate signals being sequentially formed in a multiplier. The plurality of product outputs from the multiplier are then summed in an accumulator to develop an output signal, which can then be restored back into the input data memory unless new data is to be written into the data memory. No means are provided in this system for making this recursive filter automatically and internally adapt to unknown or changing conditions in the transmission medium which may affect the input data, since this patent neither teaches nor even suggests a means of computing the filter coefficients.
Fixed parameter filters, whether recursive or transversal, are well known in the prior art and do not have an iterative process that needs to converge. An iterative process involves a means or implementation by which the weight on each tap is derived.
A second type of known non-adaptive, fixed parameter recursive filter comprises two transversal tapped delay line filters which, in combination, transversely filter the input data and then subsequently filter the output data of the recursive filter. Essentially, this is the canonical form of a recursive filter, which is well known in the art. A recursive filter can produce zeros, or finite impulse responses, with a feed-forward network, and poles, or infinite impulse responses, with a feed-back network. However, the applicability of a fixed parameter recursive filter is limited, because a design of the fixed parameters requires detailed statistical knowledge of the transmitted signals and the channel effects, just as in the fixed parameter transversal filter. These properties are often changing and, in general, are not known. To make a recursive filter a useful and powerful tool in minimizing or eliminating distortion in data signals received from an unknown or changing transmission medium, the recursive filter had to be made adaptive. The prior art difficulty in making a recursive filter adaptive was due to the fact that the convergence requirements for making the recursive filter adapt were unknown. On the other hand, transversal filter structures could be readily implemented because their convergence requirements were known.
Another type of adaptive filter is therefore an adaptive recursive filter, which is a comparatively recent development in the art. An adaptive recursive filter is much more powerful in minimizing distortion introduced into data by a transmission medium than a transversal filter, because the adaptive recursive filter has both poles and zeros whereas, as previously stated, the transversal filter has only zeros. The means used to adaptively adjust the tap gains is one of the basic features which distinguishes one adaptive recursive filter from another and, of course, from a non-adaptive, fixed parameter recursive filter. An adaptive recursive filter automatically designs itself to compute and adjust its tap weights or gains, to minimize some desired design criterion, based upon observations of the input data. Changes in the transmission medium or received data are automatically tracked by causing the tap weights to automatically change to minimize the desired design criterion. Consequently the adaptive recursive filter automatically adapts itself to these changes.
As a result, the means used to automatically adjust the tap gains or weights may be based upon the desired design criterion designed into the adaptive recursive filter. Therefore, the iterative procedure or operation, performed by the adaptive recursive filter, will converge to the solution that satisfies the desired design criterion of the filter. However, it should be noted that, although the adaptive recursive filter may be specifically designed to satisfy a desired design criterion, the filter may also satisfy other criteria as well. Examples of desired design criteria that adaptive recursive filters could be particularly designed to minimize are: to minimize the distortion introduced by the transmission medium; to minimize intersymbol interference in the transmission medium; and to use a deterministic point-wise instantaneous error criterion to automatically minimize the instantaneous error in the output data.
One known type of adaptive recursive filter is described in U.S. Pat. No. 3,716,807, which is entitled "Recursive Automatic Equalizer and Method of Operation Therefore". In this patent the filter is essentially designed to minimize line distortion and intersymbol interference in the sidelobes of the data pulse transmitted through a communications channel. The operation of this recursive equalizer system is basically directed to channel equalization by dealing primarily with the front and rear sidelobes of the pulse rather than the general filtering function of designing a processor to automatically minimize an error criterion based on the input data. The means of adjusting the tap gains of this equalizer system is a direct realization of the mathematical consequences of: (1) generating an error signal for the front part or front sidelobe of the pulse (not for an arbitrary waveform), (2) sequentially applying transversal filtering several times by using a plurality of cascaded equalizer stages in FIG. 1B, (3) generating an error signal for the rear part or rear sidelobe of the pulse (not for an arbitrary waveform), and (4) generating tail cancellation signal terms in FIG. 1C to correct the pulse. As indicated above, different error signals are utilized to respectively control the front end equalizer (FIG. 1B) and the rear end equalizer (FIG. 1C) of the equalizer system shown in FIG. 1A. In the operation of this equalizer system the feed-forward and feed-back circuits do not operate simultaneously. In the operation of FIG. 1B, the front sidelobe of the input pulse or signal is reduced to substantially zero distortion by adjusting the tap settings of successive or cascaded equalizer stages after successive iterations. After n iterations, the output signal from FIG. 1B is applied to FIG. 1C where it is modified by the reciprocal of a preselected function to substantially reduce the rear sidelobe distortion of the input signal which is to be equalized. It should be noted that both multiple feed-forward and multiple feed-back circuits are utilized in the system. It should be further noted that a non-detailed block diagram of one of the "tap adjusting means" 16, which are utilized in the front end equalizer of FIG. 1B and rear end equalizer of FIG. 1C is illustrated in FIG. 1D. In connection with the description of FIG. 1D, column 9, lines 32-33 of this U.S. Pat. No. 3,716,807, states that a detailed explanation of the tap adjust drive (22 of the tap adjusting means 16) is unnecessary. As stated previously in this application, the means used to adaptively adjust the tap gains is one of the basic features which distinguishes one adaptive recursive filter from another.
Another known type of adaptive recursive filter has recently been invented by S. A. White. This adaptive recursive filter is described in U.S. patent application Ser. No. 632,119, filed on Nov. 14, 1975. Furthermore, this adaptive recursive filter is also described by S. A. White in his article entitled "An Adaptive Recursive Digital Filter", in the publication Conference Proceedings, Ninth Asilomar Conference on Circuits, Systems, and Computers (January 1976). S. A. White's adaptive recursive filter utilizes a deterministic point-wise instantaneous error criterion to implement an algorithm to automatically adjust the tap gains, or filter coefficients, in accordance with the minimization of the instantaneous error criterion. By this means, S. A. White's adaptive recursive filter converges to a solution to satisfy this instantaneous error criterion which, as indicated previously, is a deterministic criterion. More specifically, the means for adjusting the tap gains of the filter, which is tracking an arbitrary waveform, is a direct realization of the mathematical consequences of (1) establishing a performance criterion, (2) generating an error signal, (3) computing the contribution of each tap gain error to the overall error signal, and (4) using the above three factors to selectively compute the corrections to be applied to the respective tap gains. In this filter a steepestdescent method is used to adjust the values of the filter coefficients. This criterion states that the filter coefficient which contributes the greatest error should be the filter coefficient or parameter which is most quickly corrected, while filter coefficients which contribute less to the error may be corrected more slowly.
None of the above-described or listed prior art filters or filter systems teaches an adaptive recursive least means square error filter which utilizes a least means square error criterion and updates weight vectors using a simple iterative gradient search procedure.